Advances in mobile computing and object or position sensing technologies, for example global positioning systems (GPS), radio frequency identification (RFID), Bluetooth technologies and wireless networking technologies, have facilitated the emergence of numerous applications for the continuous location and management of moving objects. These emerging applications include, for example, environmental awareness applications, object tracking and monitoring services, inventory control systems, wireless communication systems, and computer games. These applications need to track many moving objects simultaneously, including physical objects that move in two-dimensional or three-dimensional space, for example people, cars, airplanes and cargo ships. Moving objects can also be stock prices, distributed sensor readings for environmental surveillance including temperature and pressure, and public health data such as a number of sick people and a type of illness.
In order to provide tracking capabilities, the moving objects are equipped with location-awareness or remote identification equipment and are treated as points in multidimensional space whose positions change with time. The locations of these points can be tracked and queried. Tracking of points in space can be accomplished by technologies available in the art such as GPS, triangulation, and RFID systems. These tracking systems are used to locate objects or points that satisfy a given set of criteria called queries. These queries over moving objects tend to be continual, i.e., repeated periodically over time. In addition, queries can be stationary or can be associated with moving objects and hence moving. Moving queries can be general range queries, for example finding all the objects currently located inside the boundaries of a range, or k-nearest neighbors (kNN) queries, for example finding the k-nearest objects that are closest to a given point.
Previous approaches, however, assumed that the queries were stationary. A continual stationary range query specifies a spatial range together with a time interval and identifies the set of objects located within the spatial range during the specified time interval. The result of the query changes as time progresses due to the moving nature of the objects that are being queried. A moving range query has a fundamental difference when compared with a stationary query. A moving range query is associated with a moving object, called the focal object of the query, and the spatial range of the query moves together with the movement of the query's focal object. With a moving query, the identification of objects that satisfy the query over a given time period becomes more complex.
Because of the continuously changing positions of moving objects, it is very time consuming to process queries over moving objects. This problem becomes even more challenging when the queries are also moving. To speed up the query processing, various approaches have been proposed to index moving objects alone (e.g., “Indexing moving objects,” by P. K. Agarwal et al., Proceedings of ACM Symposium on Principles of Database Systems, 2000; “On indexing mobile objects,” by G. Kollios et al., Proceedings of Symposium on Principles of Database Systems, 1999), or to index queries alone (e.g., “Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects,” by S. Prabhakar et al., IEEE Transactions on Computers, 51:1124-1140, October 2002).
With both moving queries and moving objects, searching and maintaining the object index or the query index becomes exceedingly costly, because updates to the indexes are required once either the objects or the queries have moved. As an alternative to indexing, a brute force linear search, where each moving query is evaluated against every moving object, can be used to process moving queries over moving objects. This brute force approach, however, is not scalable to a large number of moving queries and moving objects. The need exists, therefore, for an efficient system and method for evaluating moving queries over moving objects. In addition, it is desired to provide the fastest access possible to large volumes of data and to preserve the spatial relationships among indexed objects such as nesting and neighborhood.